"""
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 
所使用的最少操作数。
你可以对一个单词进行如下三种操作：
    插入一个字符
    删除一个字符
    替换一个字符
"""

import numpy as np

# 状态转移方程：
# 若最后一个位置字母相同：
#   dp[i-1][j-1] => dp[i][j] 无需新的操作
#   dp[i-1][j]   => dp[i][j] 删除最后一位
#   dp[i][j-1]   => dp[i][j] 添加最后一位
# 若最后一个位置字母不同：
#   dp[i-1][j-1] => dp[i][j] 改变最后一位
#   dp[i-1][j]   => dp[i][j] 删除最后一位
#   dp[i][j-1]   => dp[i][j] 添加最后一位
class Solution:
    def minDistance(self, word1: str, word2: str, verbose=False) -> int:
        m, n = len(word1), len(word2)
        # dp = [[0]*(n+1)]*(m+1)
        dp = [[0] * (n+1) for _ in range(m+1)]
        
        for i in range(1, m+1):
            dp[i][0] = i
        for j in range(1, n+1):
            dp[0][j] = j
        for i in range(1, m+1):
            for j in range(1, n+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = 1 + min(dp[i-1][j-1]-1, min(dp[i-1][j], dp[i][j-1]))
                if word1[i-1] != word2[j-1]:
                    dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))
        
        if verbose:
            dp = np.array(dp).reshape((m+1, n+1))
            print("Alignment table of " + word1 + " and " + word2 + ":")
            print(dp)
        
        return dp[m][n]


if __name__ == "__main__":
    soln = Solution()
    print(soln.minDistance("ACTTG", "CGCAA", verbose=False))
    print(soln.minDistance("TGAGC", "GTGTAA", verbose=True))
    print(soln.minDistance("GGCTA", "CTACTG", verbose=True))
